/**
 * 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角
 * （即 grid[0][0]）。
 * 机器人尝试移动到 右下角即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
 * 返回机器人能够到达右下角的不同路径数量。  
 */

/** 
 * 简单点：障碍方案直接置0
 * dp(i,j) (i,j)的路径数
 * (i,j)如果是障碍 则dp(i,j) = 0
 * 公式：dp(i,j) = dp(i-1,j) + dp(i,j-1)
 * 初始化：dp(0,j) = 1 dp(i,0) = 1
 * @param {} obstacleGrid 
 */

var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  const dp = Array(m).fill().map(i => Array(n).fill(0));
  for(let i=0;i<m && obstacleGrid[i][0]==0;i++){
    dp[i][0]=1;
  }
  for(let j = 0; j < n &&obstacleGrid[0][j]===0; j++){
    dp[0][j] = 1;
  }
  //记住是从1开始
  for(let i = 1; i < m; i++) {
    for(let j = 1; j < n; j++) {
      dp[i][j] = obstacleGrid[i][j]===0 ? dp[i-1][j] + dp[i][j-1] : 0;
    }
  }
  return dp[m-1][n-1];
};
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] //2

/**
 * ✅review 1209
 */


console.log('不同路径v2',uniquePathsWithObstacles(obstacleGrid)); //2